#include "postier.h"


/* On défini l'infini.
Ce sera utlisé pour représenter les sommets non connectés entre eux */
#define INF 99999


	
int calculCycleEulerien(TypGraphe* G,int H)
{
	 int* tabPair = rechercheSommetsInpairs(G);
	 floydWarshall(G);
	printf("GG ta gagné\n");
}



/**
 * 
 * 
 * Fonction qui retourne le nombre de sommets impaires de g
 * 
 */
int* rechercheSommetsInpairs(TypGraphe* g){
  int i;
  int* tabPair = (int) malloc(g->nbMaxSommets * sizeof(int));
  int nbVoisins = 0; // on va compter le nombre de voisins de chaque sommets.
  
  
  int nbImpairs = 0;

  
  for(i = 0 ; i < g->nbMaxSommets ; i++){
     
    
      TypVoisins *tmp = g->listesAdjacences[i];
    /* Tant que l'on n'est pas au bout de la liste */
      while (tmp != NULL) {
	/* Contrôle qu'il y a un voisin suivant*/
        if (tmp->voisin != -1){
            /* On affiche */
	    nbVoisins++;
        }
        /* On avance d'une case */
        tmp = tmp->voisinSuivant;
    }
    tabPair[i] = nbVoisins%2; // si pair = 0 si impair = 1;
    nbImpairs += nbVoisins%2;
    nbVoisins = 0;
	
  }
  
  
  if(nbImpairs == 0){
   //cycle eulérien
    
  }else if(nbImpairs == 2){
   // le graph est un parcours eulérien
    printf("le graph est un parcours eulérien\n");
  }else if(nbImpairs == 1){
     printf("le graph a 1 sommet impaire , il va falloir le doubler pour avoir un cycle eulerien\n");
    
  }else{
    printf("le graph a %d sommets impairs, il va falloir en double %d\n",nbImpairs,nbImpairs-2);
    
  }
    
  return tabPair;
  
  
}

void floydWarshall(TypGraphe* g)
  {
    int nbSommets = g->nbMaxSommets;
    // dist est un tableau d'int à deux dimenstions comportant le plus petit chemin entre les pairs de sommets.
    int **dist;

    dist = malloc(nbSommets * sizeof(*dist));       //On alloue 'nbSommets' pointeurs.
    if(dist == NULL)
    {
      //oh non c tout cassé le programme
    }
    int i,j,k;

    for(i=0 ; i < nbSommets ; i++){
	dist[i] = malloc(nbSommets * sizeof(*(dist[i])));
	
	if(dist[i] == NULL){ // si il y a une erreur on libere toute la mémoire et on quitte
	    for(i = i-1 ; i >= 0 ; i--)    //On parcourt la boucle dans l'ordre inverse pour libérer ce qui a déjà été alloué
		free(dist[i]);
	    free(dist);                     //On libère la première dimension.

	    //oh non c tout cassé le programme
	}
    }
    
      /* Initialize the solution matrix same as input graph matrix. Or
	we can say the initial values of shortest distances are based
	on shortest paths considering no intermediate vertex. */
	  initDist(dist,g);
  
	  for(i = 0 ; i < g->nbMaxSommets ; i++){
	  for(j = 0 ; j < g->nbMaxSommets ; j++){
		printf("%d, ",dist[i][j]);
	  }
	printf("\n");
      }
      /* Add all vertices one by one to the set of intermediate vertices.
	---> Before start of a iteration, we have shortest distances between all
	pairs of vertices such that the shortest distances consider only the
	vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
	----> After the end of a iteration, vertex no. k is added to the set of
	intermediate vertices and the set becomes {0, 1, 2, .. k} */
      for (k = 0; k < nbSommets; k++)
      {
	  // Pick all vertices as source one by one
	  for (i = 0; i < nbSommets; i++)
	  {
	      // Pick all vertices as destination for the
	      // above picked source
	      for (j = 0; j < nbSommets; j++)
	      {
		  // If vertex k is on the shortest path from
		  // i to j, then update the value of dist[i][j]
		  if (dist[i][k] + dist[k][j] < dist[i][j])
		      dist[i][j] = dist[i][k] + dist[k][j];
	      }
	  }
      }
  
      // Print the shortest distance matrix
      printSolution(dist,nbSommets);
  }
  
  
    

   void initDist(int** dist, TypGraphe* g){
     // si c le meme sommet = 0
     // si ca eiste pas     = inf
     // si ca existe        = pondération
     
     int i,j;
     
     // on prépare la matrice
     for(i = 0 ; i < g->nbMaxSommets ; i++){
       for(j = 0 ; j < g->nbMaxSommets ; j++){
	 if(i == j)
	   dist[i][j] = 0;
	 else
	   dist[i][j] = INF;
       }
     }
    
    
     // et on la remplie
     for(i = 0 ; i < g->nbMaxSommets ; i++){
     
	TypVoisins *tmp = g->listesAdjacences[i];
	/* Tant que l'on n'est pas au bout de la liste */
	while (tmp != NULL) {
	  /* Contrôle qu'il y a un voisin suivant*/
	  if (tmp->voisin != -1){
	    int temp =tmp->voisin -1;
	    dist[i][temp] = tmp->ponderation;
	  }
	  /* On avance d'une case */
	  tmp = tmp->voisinSuivant;
	}
    }
 }
 
 
      /* A utility function to print solution */
  void printSolution(int** dist,int nbSommets)
  {
    printf ("Following matrix shows the shortest distances"
            " between every pair of vertices \n");
    int i,j;
    for ( i = 0; i < nbSommets; i++)
    {
        for ( j = 0; j < nbSommets; j++)
        {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
  }